public class NumDistinct {

    StringBuilder stringBuilder = new StringBuilder();
    int ans = 0;

    public int numDistinct1(String s, String t) {
        process(s, t, 0, 0);
        return ans;
    }

    public void process(String s, String t, int i, int j) {
        if (i == s.length() || j == t.length()) {
            if (j == t.length()) {
                ans += stringBuilder.toString().equals(t) ? 1 : 0;
            }
            return;
        }

        if (s.charAt(i) != t.charAt(j)) {
            process(s, t, i + 1, j);
        } else {
            stringBuilder.append(s.charAt(i));
            process(s, t, i + 1, j + 1);
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            process(s, t, i + 1, j);
        }
    }

    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        int[][] dp = new int[m][n];
        int count = 0;
        for (int i = 0; i < m; i++) {
            count += s.charAt(i) == t.charAt(0) ? 1 : 0;
            dp[i][0] = count;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (i >= j)
                    dp[i][j] = s.charAt(i) == t.charAt(j) ? dp[i - 1][j] + dp[i - 1][j - 1] : dp[i - 1][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}
